1. Field of the Invention
The present invention generally relates to the field of dynamic storage of computer systems. More particularly, the present invention relates to methods, systems, and media for managing dynamic storage.
2. Description of the Related Art
Parallel processing generally refers to performing multiple computing tasks in parallel. Traditionally, parallel processing requires multiple computer systems with the resources of each computer system dedicated to a specific task or allocated to perform a portion of a common task. However, recent advances in computer hardware and software technologies have resulted in single computer systems capable of highly complex parallel processing by partitioning the system resources to different tasks.
From a software standpoint, multithreaded, or multi-tasked, operating systems and kernels have been developed, which permit computer programs, or applications, to concurrently execute multiple tasks of the applications. Tasks generally represent execution entities defining independent paths of execution for an application. For example, for an e-commerce computer application, different tasks might be assigned to different customers so that each customer's specific e-commerce transaction can be handled simultaneously.
A significant problem that can occur in a multi-processor computer, however, is associated with the transfer of data to and from each processor, often referred to as communication cost. Such bottlenecking is particularly prevalent when processors in a computer share the same main memory since all communications between the processors and the main memory occur over a common bus or interconnect. As the number of processors in a computer increases, the communication costs involved with traffic to the main memory increases, significantly impacting a bottleneck on system performance, irrespective of the use of intermediate caches.
One solution to the problem of bottlenecking is to distribute multiple main memories across a computer, physically grouping sets of processors and caches into physical subsystems referred as “nodes”. The grouping of processors, caches and memory in each node provides relatively high-speed interaction between all of the components that are “local” to a node. The nodes are also coupled to one another over a network such as a system bus or a collection of point-to-point interconnects, thereby permitting processors in one node to access data stored in another node, thus effectively extending the overall capacity of the computer. Memory access, however, is non-uniform since the access time for data stored in a local memory (i.e., a memory resident in the same node as a microprocessor) is often significantly shorter than for data stored in a remote memory (i.e., a memory resident in another node).
Irrespective of the particular type of multi-processing architecture used, efficient utilization of the hardware resources in a computer often requires a collaborative effort between software and hardware. To ensure optimal performance, tasks are typically assigned (e.g., at the time they are created) to subsets of available computer resources in such a manner that the workload of the computer is evenly distributed among the available computer resources.
In most computer architectures, an operating system or kernel, and in particular, application code therein is responsible for allocating memory and processor resources to applications and their constituent tasks. In a multi-node architecture, for example, tasks can be assigned “home nodes”, and the operating system or kernel will attempt to allocate memory and processor resources from a task's assigned home node to optimize hardware performance, minimize communication costs, and balance workload across the various nodes.
Dynamic storage, on the other hand, is managed separately from other resources. Dynamic storage involves allocating and freeing objects dynamically for use by an application and is accessed often by complex applications when, for example, the number and size of objects needed by the application are not known before compilation, or an object is too large to fit into a stack that is allocated during compilation. Heaps maintain dynamic storage for a computer system and are located within the memory of the nodes. The physical location of a heap with respect to the task using the heap, is critical to access times associated with dynamic storage, especially when considering the traffic on a system bus, and is thus, critical to the execution speed of tasks and applications in general. However, allocations for dynamic storage are physically distributed in heaps throughout the nodes based upon the availability of the dynamic storage without regard to the node within which a task utilizing dynamic storage is executed.